#include <iostream>     // std::cout, std::cin
#include <algorithm>    // std::sort
#include <vector>       // std::vector
#include <	>       // std::vector

#include "ej2.h"

using namespace std;

Caballo::Caballo(int _id, int _x , int _y, int _cant): id(_id), x(_x), y(_y), cant(_cant){}

Casilla::Casilla(int _x, int _y, int _idAux, int _idActual, int _acum, bool _lleganTodos, bool _llegaUlt): x(_x), y(_y), idAux(_idAux), idActual(_idActual), acum(_acum), lleganTodos(_lleganTodos), llegaUlt(_llegaUlt){}

Aux::Aux(int _posx, int _posy , int _cantSaltos): posx(_posx), posy(_posy), cantSaltos(_cantSaltos){}

Tablero::Tablero(int n, int k): tam(n), cantTotCab(k){
 matriz.resize(n);

for(int i=0; i<n ; i++){
	for(int j=0; j<n ; j++){
		matriz[i].push_back(Casilla(i, j, -1, -1, 0, true, false));
		}
	}
}


//imprime la cantidad de caballos por cada casilla en el estado inicial
void imprimirTablero(Tablero &t, vector<Caballo> &c){
int n = t.tam;
cout << "el tablero tiene " << n << " x " << n  << ": " << endl;
for (int i=0; i<n; i++){
	for (int j=0; j<n; j++){
		if (t.matriz[i][j].idAux != -1){
		cout << " ||  "<< i<<","<<j<< ": " << c[t.matriz[i][j].idAux].cant << "  | " ;
		}
		else{
		cout << " ||  "<< i<<","<<j<< ": " << 0 << "  | " ;
		}
		}
		cout << endl;	
	}	

}


//imprime en cada casilla la cantidad de saltos totales de todos los caballos
void imprimirTablero2(Tablero &t){
int n = t.tam;
//cout << "el tablero tiene " << n << " x " << n  << ": " << endl;
cout << "se mostrará la cantidad de saltos total de los caballos para cada casilla" << endl;
for (int i=0; i<n; i++){
	for (int j=0; j<n; j++){
		cout << " |  " << t.matriz[i][j].acum << "  | " ;
		
		}
		cout << endl;	
	}	

}

//imprime solo las casillas donde llegaron todos los caballos con los resultados de los saltos totales:
void imprimirTablero3(Tablero &t){
int n = t.tam;
cout << "el tablero tiene " << n << " x " << n  << ": " << endl;
	for (int i=0; i<n; i++){
		for (int j=0; j<n; j++){
			if (t.matriz[i][j].lleganTodos &&  t.matriz[i][j].llegaUlt){
			cout << " |  "<< t.matriz[i][j].acum << "  | " ;
			}
			else{
			cout << " |  " << -1 << "  | " ;
			}
		}
		cout << endl;	
	}	

}


//imprime la lista de los caballos (por simplicidad si hay mas de un caballo inicialmente en una casilla, solo se le asigna un id y una cantidad de caballos en dicha casilla)
void imprimirCaballos(vector<Caballo> &c){
cout << "*******************************************" << endl;
cout << "los caballos en el tablero son los siguintes:" << endl;
	for (unsigned int i=0; i<c.size(); i++){
		cout << "||caballo id: " << c[i].id << " en la posicion (x,y)=("<<c[i].x<<","<<c[i].y<<") una cantidad igual a " << c[i].cant<< ".|| "<< endl;; 
	}
	cout << "******************************************************"<<endl;
}

void devolverResultado (Tablero &t){
	int f,c,m_aux; 
	int m = 0;
	bool a = false;
	int n = t.tam;
		
	for (int i=0; i < n ; i++){
		for (int j=0; j < n ; j++){
			if (t.matriz[i][j].lleganTodos &&  t.matriz[i][j].llegaUlt){
				m_aux = t.matriz[i][j].acum ;
				if (a){
					if (m_aux < m){
						m = m_aux;
						f = i;
						c = j;
					}
				}
				else{
					a = true;
					m = m_aux;
					f = i;
					c = j;
				}
			}
		}	
	}
	
	cout << "a continuacion se imprimira el resultado, si hay solucion se imprimirá -- f c m -- donde f es la fila c columna y m cantidad de saltos minimo " << endl;
	cout << "si no existiera solucion se imprimira una linea con un -- no --"	<< endl;
	if (a){
		cout << f << " " << c << " " <<  m << endl;
	}
	else{
		cout << "no" << endl;
	}

}

//verifica si el si las coordenadas de fila y columna son validas para el tablero
bool esValido(Tablero &t, int x, int y){	//O(1)
return (x >=0) && (x<t.tam) && (y>=0) && (y<t.tam); 
}


void caminoCorto(Tablero &t, Caballo c, int ultimoCaballo){		//O(n^2) donde n= cant de filas de t
//cada casilla ocupada inicialmente por uno o mas caballos esta asociada a un id_caballo del arreglo "caballos"
//a cada elemento del arreglo me fijo :las coordenadas en el tablero (px, py), el id, la cantidad de caballos en esa casilla inicialmente (cant)
int px= c.x;
int py= c.y;
int id = c.id;
int cant = c.cant;
int x, y;

//un arreglo para encolar solo las casillas que no han sido visitadas por el actual id_caballo
queue< Aux > cola;
//encolo la primer casilla
cola.push(Aux(px,py,0)); 

//Desde cada casilla que esta en la cola voy a querer visitar sus vecinos
//vecinos = [(x-2,y-1),(x-2,y+1),\(x-1,y-2),(x-1,y+2),\(x+1,y-2),(x+1,y+2),\(x+2,y-1),(x+2,y+1)]

//el atributo "lleganTodos" sirve para saber si alguna casilla en el medio del llenado no fue llenada por algun id_caballo
if(t.matriz[px][py].idActual != id-1){
	t.matriz[px][py].lleganTodos = false;
}
//llegaUlt me dice si el ultimo id_Caballollego hasta la casilla
if(id==ultimoCaballo){
	t.matriz[px][py].llegaUlt = true;
}
t.matriz[px][py].idActual = id;
int s;

//si "n" es la cantidad de filas (o columnas) del tablero t
//y siempre encolo solo casillas a las que no he visitado de manera que como mucho encolo n^2 
	while(!cola.empty()){		//O(n^2)
		//desecolo
		Aux a = cola.front();
		cola.pop();
		px = a.posx;
		py = a.posy;
		s = a.cantSaltos + 1;
		
		//ahora por cada casilla me fijo en las 8 casillas siguientes a partir de ahi
		//para cada vecino realizo operaciones en O(1) y como son 8 vecinos la complejidad dentro de cada iteracion en el ciclo es 8*O(1)
			//primer vecino:
			x=px+1;
			y=py+2;
			if (esValido(t,x,y)){
				//si el id_caballo actual ya lo visito no vuelvo a visitarlo
				if (t.matriz[x][y].idActual != id){
					t.matriz[x][y].acum += (cant*s);
					cola.push (Aux(x,y,s));
					//si el anterior caballo que llego no fue el de id -1 entonces seguramente no llegan todos
					if(t.matriz[x][y].idActual != id-1){
						t.matriz[x][y].lleganTodos = false;
					}
					//marco el id_caballo actual para no volver a visitar esta casilla
					t.matriz[x][y].idActual = id;
					//si el id_caballo que esta recorriendo el tablero es el ultimo completo "llegaUlt"
					if(id==ultimoCaballo){
						t.matriz[x][y].llegaUlt = true;
					}
				}
			}
				
			//segundo vecino:
			x=px+1;
			y=py-2;
			if (esValido(t,x,y)){
				//si el id_caballo actual ya lo visito no vuelvo a visitarlo
				if (t.matriz[x][y].idActual != id){
					t.matriz[x][y].acum += (cant*s);
					cola.push (Aux(x,y,s));
					//si el anterior caballo que llego no fue el de id -1 entonces seguramente no llegan todos
					if(t.matriz[x][y].idActual != id-1){
						t.matriz[x][y].lleganTodos = false;
					}
					//marco el id_caballo actual para no volver a visitar esta casilla
					t.matriz[x][y].idActual = id;
					//si el id_caballo que esta recorriendo el tablero es el ultimo completo "llegaUlt"
					if(id==ultimoCaballo){
						t.matriz[x][y].llegaUlt = true;
					}
				}
			}
			
			//tercer vecino:	
			x=px-1;
			y=py+2;
			if (esValido(t,x,y)){
				//si el id_caballo actual ya lo visito no vuelvo a visitarlo
				if (t.matriz[x][y].idActual != id){
					t.matriz[x][y].acum += (cant*s);
					cola.push (Aux(x,y,s));
					//si el anterior caballo que llego no fue el de id -1 entonces seguramente no llegan todos
					if(t.matriz[x][y].idActual != id-1){
						t.matriz[x][y].lleganTodos = false;
					}
					//marco el id_caballo actual para no volver a visitar esta casilla
					t.matriz[x][y].idActual = id;
					//si el id_caballo que esta recorriendo el tablero es el ultimo completo "llegaUlt"
					if(id==ultimoCaballo){
						t.matriz[x][y].llegaUlt = true;
					}
				}
			}
			
			//cuarto vecino:	
			x=px-1;
			y=py-2;
			if (esValido(t,x,y)){
				//si el id_caballo actual ya lo visito no vuelvo a visitarlo
				if (t.matriz[x][y].idActual != id){
					t.matriz[x][y].acum += (cant*s);
					cola.push (Aux(x,y,s));
					//si el anterior caballo que llego no fue el de id -1 entonces seguramente no llegan todos
					if(t.matriz[x][y].idActual != id-1){
						t.matriz[x][y].lleganTodos = false;
					}
					//marco el id_caballo actual para no volver a visitar esta casilla
					t.matriz[x][y].idActual = id;
					//si el id_caballo que esta recorriendo el tablero es el ultimo completo "llegaUlt"
					if(id==ultimoCaballo){
						t.matriz[x][y].llegaUlt = true;
					}
				}
			}
			
			//quinto vecino	
			x=px+2;
			y=py+1;
			if (esValido(t,x,y)){
				//si el id_caballo actual ya lo visito no vuelvo a visitarlo
				if (t.matriz[x][y].idActual != id){
					t.matriz[x][y].acum += (cant*s);
					cola.push (Aux(x,y,s));
					//si el anterior caballo que llego no fue el de id -1 entonces seguramente no llegan todos
					if(t.matriz[x][y].idActual != id-1){
						t.matriz[x][y].lleganTodos = false;
					}
					//marco el id_caballo actual para no volver a visitar esta casilla
					t.matriz[x][y].idActual = id;
					//si el id_caballo que esta recorriendo el tablero es el ultimo completo "llegaUlt"
					if(id==ultimoCaballo){
						t.matriz[x][y].llegaUlt = true;
					}
				}
			}
				
			//sexto vecino:
			x=px+2;
			y=py-1;
			if (esValido(t,x,y)){
				//si el id_caballo actual ya lo visito no vuelvo a visitarlo
				if (t.matriz[x][y].idActual != id){
					t.matriz[x][y].acum += (cant*s);
					cola.push (Aux(x,y,s));
					//si el anterior caballo que llego no fue el de id -1 entonces seguramente no llegan todos
					if(t.matriz[x][y].idActual != id-1){
						t.matriz[x][y].lleganTodos = false;
					}
					//marco el id_caballo actual para no volver a visitar esta casilla
					t.matriz[x][y].idActual = id;
					//si el id_caballo que esta recorriendo el tablero es el ultimo completo "llegaUlt"
					if(id==ultimoCaballo){
						t.matriz[x][y].llegaUlt = true;
					}
				}
			}
			
			//septimo vecino	
			x=px-2;
			y=py+1;
			if (esValido(t,x,y)){
				//si el id_caballo actual ya lo visito no vuelvo a visitarlo
				if (t.matriz[x][y].idActual != id){
					t.matriz[x][y].acum += (cant*s);
					cola.push (Aux(x,y,s));
					//si el anterior caballo que llego no fue el de id -1 entonces seguramente no llegan todos
					if(t.matriz[x][y].idActual != id-1){
						t.matriz[x][y].lleganTodos = false;
					}
					//marco el id_caballo actual para no volver a visitar esta casilla
					t.matriz[x][y].idActual = id;
					//si el id_caballo que esta recorriendo el tablero es el ultimo completo "llegaUlt"
					if(id==ultimoCaballo){
						t.matriz[x][y].llegaUlt = true;
					}
				}
			}
			
			//octavo vecino	
			x=px-2;
			y=py-1;
			if (esValido(t,x,y)){
				//si el id_caballo actual ya lo visito no vuelvo a visitarlo
				if (t.matriz[x][y].idActual != id){
					t.matriz[x][y].acum += (cant*s);
					cola.push (Aux(x,y,s));
					//si el anterior caballo que llego no fue el de id -1 entonces seguramente no llegan todos
					if(t.matriz[x][y].idActual != id-1){
						t.matriz[x][y].lleganTodos = false;
					}
					//marco el id_caballo actual para no volver a visitar esta casilla
					t.matriz[x][y].idActual = id;
					//si el id_caballo que esta recorriendo el tablero es el ultimo completo "llegaUlt"
					if(id==ultimoCaballo){
						t.matriz[x][y].llegaUlt = true;
					}
				}
			}
	}

}


/*
 if (t.matriz[x][y].idActual != id){
	t.matriz[x][y].acum += (cant*s);
	t.matriz[x][y].idActual = id;
	cola.push (Aux(x,y,s));
	//cout <<"sumo x+1 y a y-2 .posiciones: (x,y)= ("<< x <<","<< y<<")" <<  endl;
	//imprimirTablero2(t);
}

*/


void ej2(){
int n, k, f, c, l;
int id = 0;
vector <Caballo>  caballos;
//"caballos" es un arreglo de caballos que ocupan inicialmente cada casilla se identifican con un "id"
// si hay mas de un caballo en una casilla, solo agrego uno, le asocio una id y aumento la cantidad de caballos asociada a esa casilla (cant)
cin >> n;
cin >> k;		
//creo el tablero
Tablero t(n, k);
	//ingreso los datos y lleno las casillas y el arreglo "caballos"
	for (int i=0; i<k; i++){
		cin >> f;
		cin >> c;
		l = t.matriz[f][c].idAux;
		if(l != -1){
		caballos[l].cant++;
		}
		else {
		t.matriz[f][c].idAux = id;
		caballos.push_back(Caballo(id,f,c,1));
		id++;
		}
	}

//imprimo el tablero y el arreglo "caballos" para ver graficamente la distribucion de los mismos en el tablero
imprimirTablero(t, caballos);
imprimirCaballos(caballos);
	
	//"caballos" representa en cada posicion una casilla ocupada inicialmente por uno o mas caballos
	//a cada elemento del arreglo caballos voy a referirme como id_caballo ya que cada uno tiene un id diferente y ordenado
	//cantidad de casillas ocupadas inicialmnte
	int cantCasillasOcupadas = caballos.size();
	
	//por cada id_caballo comienzo a llenar todas las casillas con los saltos minimos
	//si k = cantidad de casillas ocupadas inicialmente
	//n = catidad de filas (o columnas) del tablero t entonces =>
	
	for (int i=0; i<cantCasillasOcupadas; i++){	//O(k*(n*n))
		caminoCorto(t, caballos[i], cantCasillasOcupadas-1);
	} 

//muestro el estado final del tablero con la sumatoria de saltos minimos
cout << "sumatoria de los saltos minimos que tienen que hacer todos los caballos para llegar a la casilla, no considera si no llegan todos:" << endl;
imprimirTablero2(t);
cout<< "sumatoria del total de saltos minimos por casilla de todos los caballos. Si no llegan todos m muestra -1"<<endl;
imprimirTablero3(t);
devolverResultado(t);
	
	cout << "***************************fin del proceso*********************************************************" << endl;
	cout << "***************************************************************************************************" << endl;
}


int main()
{
  while(cin.peek() != 48) {
	 cout << "******************************************ingrese valores para comenzar*****************************" << endl;
    ej2();
    cin.get();
  }
   return 0;
}
